10481. A*B*C

Для заданного натурального числа k найдите количество троек натуральных чисел (a, b, c) таких что a * b * c ≤ k. Две тройки, которые отличаются только порядком, считаются разными.

Вход. Одно целое число k (1 ≤ k ≤ 2 * 10⁵).

Выход. Выведите количество троек натуральных чисел (a, b, c) таких что a * b * c ≤ k.

Пример входа 1	Пример выхода 1
2	4
Пример входа 2	Пример выхода 2
10	53

РЕШЕНИЕ

перебор

Анализ алгоритма

Переберем значение a от 1 до k. Переберем b от 1 и до тех пор пока a * b ≤ k. Для каждой такой пары (a, b) существует в точности значений c таких что a * b * c ≤ k. Осталось просуммировать эти значения c.

Пример

В первом примере тройками, удовлетворяющими неравенству a * b * c ≤ 2, будут:

· (1, 1, 1), так как 1 * 1 * 1 ≤ 2;

· (2, 1, 1) и ее перестановки (1, 2, 1), (1, 1, 2), так как 2 * 1 * 1 ≤ 2;

Рассмотрим второй пример. Перебираются все возможные пары натуральных чисел (a, b), для которых a * b ≤ 10. Например, для пары (a, b) = (2, 2) существует в точности = = 2 значения с, для которых a * b * c ≤ 10. Такими значениями с будут 1 и 2, так как 2 * 2 * 1 ≤ 10 и 2 * 2 * 2 ≤ 10.

Реализация алгоритма

Читаем входное значение k.

scanf("%lld", &k);

В переменной res подсчитываем количество искомых троек.

res = 0;

Запускаем перебор по всем натуральным a и b, для которых a * b ≤ k.

for (a = 1; a <= k; a++)

for (b = 1; a * b <= k; b++)

{

Прибавим к результату res значение .

c = k / (a * b);

res += c;

}

Выводим ответ.

printf("%lld", res);

Python реализация

Читаем входное значение k.

k = int(input())

В переменной res подсчитываем количество искомых троек.

res = 0

Запускаем перебор по a от 1 до k.

for a in range(1, k + 1):

Установим b = 1 и совершаем перебор по b пока a * b ≤ k.

b = 1

while a * b <= k:

Прибавим к результату res значение .

c = k // (a * b)

res += c

b += 1

Выводим ответ.

print(res)